package main.LeetCode75.Level1;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Day6_Day10 {
    public static void main(String[] args) {
        System.out.println("**************************Day6**************************");
        System.out.println("Question589：N 叉树的前序遍历");
        System.out.println("Question102：二叉树的层序遍历");
        System.out.println("**************************Day7**************************");
        System.out.println("Question704：二分查找");
        System.out.println("Question278：第一个错误的版本");
        System.out.println("**************************Day8**************************");
        System.out.println("Question98：验证二叉搜索树");
        System.out.println("Question235：二叉搜索树的最近公共祖先");
        System.out.println("**************************Day9**************************");
        System.out.println("Question733：图像渲染");
        System.out.println("Question200：岛屿数量");
        System.out.println("**************************Day10**************************");
        System.out.println("Question509：斐波那契数");
        System.out.println("Question70：爬楼梯");
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
    this.val = val;
    this.left = left;
    this.right = right;
    }
}

class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
};

class Question589{
    public void process(Node root, List<Integer> list){
        if (root==null) return;
        list.add(root.val);
        for (Node cur: root.children) process(cur,list);
    }
    public List<Integer> preorder(Node root) {
        List<Integer> list=new ArrayList<>();
        process(root,list);
        return list;
    }
}

class Question102{
    public List<List<Integer>> levelOrder(TreeNode root) {//map中存在同层顺序问题
        List<List<Integer>> ret = new ArrayList<List<Integer>>();
        if (root == null) return ret;
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            List<Integer> level = new ArrayList<Integer>();
            int currentLevelSize = queue.size();
            for (int i = 1; i <= currentLevelSize; ++i) {
                TreeNode node = queue.poll();
                level.add(node.val);
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            ret.add(level);
        }
        return ret;
    }
}

class Question704{
    public int search(int[] nums, int target) {
        int result=-1,left=0,right= nums.length-1;
        while (left<=right){
            int mid=(left+right)/2;
            if (nums[mid]==target) {
                result=mid;
                break;
            } else if (nums[mid]<target) left=mid+1;
            else right=mid-1;
        }
        return result;
    }
}

class Question278{
    public int firstBadVersion(int n) {
        int left = 1, right = n;
//        while (left < right) { // 循环直至区间左右端点相同
//            int mid = left + (right - left) / 2; // 防止计算时溢出
//            if (isBadVersion(mid)) {
//                right = mid; // 答案在区间 [left, mid] 中
//            } else {
//                left = mid + 1; // 答案在区间 [mid+1, right] 中
//            }
//        }
        // 此时有 left == right，区间缩为一个点，即为答案
        return left;
    }
}

class Question98{
    public class Info{
        public boolean isSearch;
        public Long max;//左子树最大值
        public Long min;//右子树最小值
        public Info(boolean isSearch,Long max,Long min){
            this.isSearch=isSearch;
            this.max=max;
            this.min=min;
        }
    }
    public Info process(TreeNode root){
        if (root==null) return new Info(true,Long.MIN_VALUE,Long.MAX_VALUE);
        Info left=process(root.left);
        Info right=process(root.right);
        boolean isSearch=false;
        Long max= Math.max(root.val, right.max);
        Long min= Math.min(root.val, left.min);
        if (left.isSearch&& right.isSearch&& root.val> left.max&&root.val< right.min){
            isSearch=true;
            return new Info(isSearch,max,min);
        }else return new Info(isSearch,max,min);
    }
    public boolean isValidBST(TreeNode root) {
        return process(root).isSearch;
    }
}

class Question235{
    public class Info{
        public boolean isExistNode1;
        public boolean isExistNode2;
        public TreeNode commonFather;
        public Info(boolean isExistNode1, boolean isExistNode2, TreeNode commonFather){
            this.isExistNode1=isExistNode1;
            this.isExistNode2=isExistNode2;
            this.commonFather=commonFather;
        }
    }
    public Info process(TreeNode root, TreeNode p, TreeNode q){
        if (root==null) return new Info(false,false,null);
        Info left=process(root.left, p, q);//左子树信息
        Info right=process(root.right, p, q);//右子树信息
        if (left.commonFather!=null||right.commonFather!=null){//其中一个子树中已经存在公共祖先
            return left.commonFather==null ? right : left;//将存在公共祖先的子树信息返回
        }
        boolean node1=false,node2=false;
        TreeNode temp=null;
        if (root==p|| left.isExistNode1==true || right.isExistNode1==true) node1=true;//当其中一个子树中存在p或当前节点为p
        if (root==q|| left.isExistNode2==true || right.isExistNode2==true) node2=true;//当其中一个子树中存在q或当前节点为q
        if (node1&&node2){//当本节点即为公共祖先时
            temp=root;
        }
        return new Info(node1,node2,temp);
    }
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        return process(root,p,q).commonFather;
    }
}

class Question733{
    int newColor=0;
    int intiColor=0;
    public void process(int[][] image,int[][] result,int row,int col){
        int r= image.length,c=image[0].length;
        result[row][col]=newColor;
        if (row-1>=0&&image[row-1][col]==intiColor&&result[row-1][col]!=newColor) process(image,result,row-1,col);//上
        if (row+1<r&&image[row+1][col]==intiColor&&result[row+1][col]!=newColor) process(image,result,row+1,col);//下
        if (col-1>=0&&image[row][col-1]==intiColor&&result[row][col-1]!=newColor) process(image,result,row,col-1);//左
        if (col+1<c&&image[row][col+1]==intiColor&&result[row][col+1]!=newColor) process(image,result,row,col+1);//右
    }
    public int[][] floodFill(int[][] image, int sr, int sc, int color) {
        int row= image.length,col=image[0].length;
        int[][] result=new int[row][col];
        for (int i=0;i<row;i++){
            for (int j=0;j<col;j++)
                result[i][j]=image[i][j];
        }
        intiColor=image[sr][sc];
        newColor=color;
        process(image,result,sr,sc);
        return result;
    }
}

class Question200{
    public void process(char[][] grid,int i,int j){
        int row=grid.length,col=grid[0].length;
        grid[i][j]='0';
        if (i-1>=0&&grid[i-1][j]=='1') process(grid,i-1,j);
        if (i+1<row&&grid[i+1][j]=='1') process(grid,i+1,j);
        if (j-1>=0&&grid[i][j-1]=='1') process(grid,i,j-1);
        if (j+1<col&&grid[i][j+1]=='1') process(grid,i,j+1);
    }
    public int numIslands(char[][] grid) {
        int row=grid.length,col=grid[0].length,count=0;
        for (int i=0;i<row;i++){
            for (int j=0;j<col;j++){
                if (grid[i][j]=='1'){
                    count++;
                    process(grid,i,j);
                }
            }
        }
        return count;
    }
}

class Question509{
    public int fib(int n) {
        int head=0,end=1,result=1;
        for (int i=2;i<=n;i++){
            result=head+end;
            head=end;
            end=result;
        }
        if (n==0) result=0;
        else if (n==1) result=1;
        return result;
    }
}

class Question70{
    public int climbStairs(int n) {
        int num=0,head=1,end=2,result=0;
        for (int i=3;i<=n;i++){
            result=head+end;
            head=end;
            end=result;
        }
        if (n==1) result=1;
        else if (n==2) result=2;
        return result;
    }
}